/*
Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.



*/
#include <iostream>
#include "print.h"
#include <vector>
#include <algorithm>

using namespace std;


class Solution {
public:
	int res;
	vector<int> queens;
	int totalNQueens(int n) {
		res = 0;
		if (n<=1)
		{
			return n;
		}
		queens.resize(n);
		for (int i = 0; i < n; i++)
		{
			queens[i] = i;
		}

		nQueensCore(queens,n,0);
		return res;
	}

	void nQueensCore(vector<int> &queens, int n, int st)
	{
		if (st == n)
		{
			++res;
		}
		int temp, i, j;
		for ( i = st; i < n; i++)
		{
			temp = queens[st];
			queens[st] = queens[i];
			queens[i] = temp;

			for ( j = 0; j < st; j++)
			{
				if (abs(queens[st]-queens[j]) == abs(st-j))
					break;

			}
			if (j == st) nQueensCore(queens, n, st + 1);
			temp = queens[st];
			queens[st] = queens[i];
			queens[i] = temp;
			

			
		}

	}

};


int main()
{
	int a[] = { 1, 1, 2 };
	vector<int> nums(a, a + sizeof(a) / sizeof(int));

	vector<vector<string> > res;
	Solution s;
	int n = 4;
	int re = s.totalNQueens(n);


	system("pause");
	return 0;
}